{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, [])"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 1.0\n",
    "# 判断素数\n",
    "def is_prime(a):\n",
    "    if a < 2 :\n",
    "        return False, []\n",
    "    elif a == 2:\n",
    "        return True, []\n",
    "    \n",
    "    # 用从 2 到 a-1 之间的每个数除以 a, 得出能整除 a 的数\n",
    "    divisors = [x for x in range(2, a) if a % x == 0]\n",
    "    return len(divisors) == 0, divisors\n",
    "\n",
    "\n",
    "is_prime(11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 以内共有168个素数\n",
      "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n"
     ]
    }
   ],
   "source": [
    "# 2.0\n",
    "# 判断素数改进\n",
    "\n",
    "import math\n",
    "def is_prime_2(a):\n",
    "    # 判断 a 是否是素数（2.0 版）\n",
    "    # param a: 大于 0 的整数\n",
    "    # return\n",
    "    \n",
    "    if a == 2:                 # 2 是素数\n",
    "        return True\n",
    "    elif a < 2 or a & 1 == 0: # 小于 2 或偶数\n",
    "        return False\n",
    "    m = int(math.sqrt(a))\n",
    "    for q in range(3, m + 1, 2): # 只判断奇数\n",
    "        if a % q == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "    \n",
    "primes = [x for x in list(range(1000)) if is_prime_2(x)]\n",
    "print('1000 以内共有{}个素数'.format(len(primes)))\n",
    "print(primes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[829, 839]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "def is_prime_2(a):\n",
    "    # 判断 a 是否是素数（2.0 版）\n",
    "    # param a: 大于 0 的整数\n",
    "    # return\n",
    "    \n",
    "    if a == 2:                 # 2 是素数\n",
    "        return True\n",
    "    elif a < 2 or a & 1 == 0: # 小于 2 或偶数\n",
    "        return False\n",
    "    m = int(math.sqrt(a))\n",
    "    for q in range(3, m + 1, 2): # 只判断奇数\n",
    "        if a % q == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "# 整数的素因子分解\n",
    "def prime_dividion(a):\n",
    "    \"\"\"\n",
    "    :params a: 大于 1 的整数\n",
    "    :return: 素因子表达式\n",
    "    \"\"\"\n",
    "    \n",
    "    if is_prime_2(a):\n",
    "        return [a] # 素数的素因子分解等于素数本身\n",
    "    result = []\n",
    "    divisors = [x for x in range(2, a) if a % x == 0 and is_prime_2(x)] # a 的所有素数因子\n",
    "    for divisor in divisors:\n",
    "        while True:\n",
    "            if a % divisor != 0:\n",
    "                break\n",
    "            result.append(divisor)\n",
    "            a /= divisor\n",
    "    return result\n",
    "\n",
    "prime_dividion(695531)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "GCD(30, 10) = 10\n",
      "GCD(14, -6) = 2\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "\n",
    "def show_gcd(a, b):\n",
    "    \"\"\"\n",
    "    展示两个数的最大公约数\n",
    "    \"\"\"\n",
    "    gcd = math.gcd(a, b)\n",
    "    print('GCD({0}, {1}) = {2}'.format(a, b, gcd))\n",
    "    \n",
    "show_gcd(30, 10)\n",
    "show_gcd(14, -6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 辗转相除法\n",
    "欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。\n",
    "基本算法：设a= bq + r，其中 a， b，q，r 都是整数，则 gcd(a,b) = gcd(b,r)，即 gcd(a,b) = gcd(b,a%b)\n",
    "\n",
    "\n",
    "\n",
    "#更相减损法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5x + 10y = 5, (x, y) =  (1, 0)\n",
      "5x + 11y = 1, (x, y) =  (-2, 1)\n",
      "16x + 24y = 8, (x, y) =  (-1, 1)\n"
     ]
    }
   ],
   "source": [
    "# 欧几里得算法扩展\n",
    "# 定理：若a和b为正整数，则存在整数 x, y 使得 gcd(a,b) = ax + by;\n",
    "\n",
    "def extEculid(a, b): \n",
    "    if b == 0:\n",
    "        x, y = 1, 0 # b = 0 是的一组特解\n",
    "        return x, y\n",
    "    x, y = extEculid(b , a % b)\n",
    "    return y, x - (a // b) * y\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print('5x + 10y = 5, (x, y) = ',extEculid(5, 10))\n",
    "    print('5x + 11y = 1, (x, y) = ',extEculid(5, 11))\n",
    "    print('16x + 24y = 8, (x, y) = ',extEculid(16, 24))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "扩展欧几里德算法的应用主要有以下三方面：\n",
    "\n",
    "（1）求解不定方程；\n",
    "\n",
    "（2）求解模的逆元；\n",
    "\n",
    "（3）求解模线性方程（线性同余方程）；"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
